package danran.bfs;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * @Classname NumSquares
 * @Description TODO
 * @Date 2021/8/27 19:38
 * @Created by ASUS
 */
public class NumSquares {

    public static void main(String[] args) {
        System.out.println(new NumSquares().numSquares(1000));
    }

    public int numSquares(int n) {
        double sqrt = Math.sqrt(n);
        int m = (int) sqrt;
        int[] sqs = generate(m);
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0});
        Set<Integer> set = new HashSet<>();
        while (!q.isEmpty()) {
            int[] node = q.poll();
            for (int sq : sqs) {
                int newVal = node[0] + sq;
                if (newVal == n) return node[1] + 1;
                if (newVal < n ) q.offer(new int[]{newVal, node[1] + 1});
            }
        }
        return 0;
    }


    public int numSquares1(int n) {
        double sqrt = Math.sqrt(n);
        int m = (int) sqrt;
        int[] sqs = generate(m);
        Queue<Integer> q = new ArrayDeque<>();
        Queue<Integer> q2 = new ArrayDeque<>();
        for (int s : sqs) {
            q.offer(s);
            q2.offer(n);
        }
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            step++;
            for (int i = size - 1; i >= 0; i--) {
                Integer cur = q.poll();
                Integer remain = q2.poll();
                if (remain - cur == 0) return step;
                for (int s : sqs) {
                    q.offer(s);
                    q2.offer(remain - cur);
                }
            }
        }
        return step;
    }

    public int[] generate(int m) {
        int[] ans = new int[m];
        for (int i = 1; i <= m; i++) {
            ans[i - 1] = i * i;
        }
        return ans;
    }
}
